Heap sort（堆排序）：一种基于堆（heap）这种数据结构的比较排序算法。通常先把数组建成最大堆，然后反复把堆顶（最大值）与末尾元素交换、缩小堆的范围并重新调整堆，从而得到升序结果。时间复杂度一般为 O(n log n)，且可实现为原地排序（额外空间开销小）。
/hiːp sɔːrt/
Heap sort is easy to implement once you understand heaps.
堆排序一旦你理解了堆，就很容易实现。
Although quicksort is often faster in practice, heap sort guarantees O(n log n) time and can sort the array in place.
虽然快速排序在实践中常常更快，但堆排序能保证 O(n log n) 的时间复杂度，并且可以原地对数组排序。
heap 原意为“堆、堆叠”，在计算机科学中引申为一种“像堆一样有层次结构的树形数据结构”（堆）。sort 来自“整理、分类”。“heap sort”字面意思就是“用堆来进行排序”，强调其核心方法是借助堆的性质来选出最大（或最小）元素并完成排序。
Select Language